package leetcode_tag.树;

import leetcode.TreeNode;

// 找到路径的最大值
// 递归找到一条路径
public class LeetCode124 {

    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }

    private int helper(TreeNode node) {
        if (node == null)
            return 0;
        int left = Math.max(helper(node.left), 0);
        int right = Math.max(helper(node.right), 0);
        int nodeValue = node.val + left + right;
        max = Math.max(nodeValue, max);
        return node.val + Math.max(left, right);
    }
}
